本篇同步發布於Blog:[解題] LeetCode - 122 Best Time to Buy and Sell Stock II

平台：

LeetCode

題號：

122 - Best Time to Buy and Sell Stock II

題目連結：

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

題目說明：

        輸入1個整數的陣列prices，代表每天的股票價位，求獲利最高的答案。

        比如範例輸入的 [7,1,5,3,6,4]，最佳的獲利方式是第2天買1元、第3天賣出5元，賺4元，再加上第4天買3元、第5天賣6元，賺3元。總計賺7元。

解題方法：

   　先思考如果用暴力法，變成要從第i天往後算i + 1 ~ N最大的解，再求其他第j天往後算j + 1 ~ N的最佳解，時間複雜度需要O(n^n)。

轉換更有效率的解，只需要求每天第i天的價位 > 第i-1天的價位，就把這價位差做累加，最終的累加值為答案。

難度為Easy

程式碼 (C++ 與 C#)：

class Solution {
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxAns = 0;
        for(int i = 1 ; i < prices.size();++i){
            if(prices[i] > prices[i-1]){
                maxAns += prices[i] - prices[i-1];
            }
        }
        
        return maxAns;
    }
};

int main() {
	
	vector<int> prices{7,1,5,3,6,4};
	Solution sol;
	cout << sol.maxProfit(prices) << endl;
	return 0;
}

using System;

namespace LeetCode122
{
    public class Solution {
		public int MaxProfit(int[] prices) {
			int maxAns = 0;
			for(int i = 1 ; i < prices.Length;++i){
				if(prices[i] > prices[i-1]){
					maxAns += prices[i] - prices[i-1];
				}
			}
			
			return maxAns;
		}
	}
	
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] prices = new int[]{7,1,5,3,6,4};
            Console.WriteLine(new Solution().MaxProfit(prices));
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/100-199/122.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/100-199/122.cs